package 每日一题;

import common.GeneralFunction;

public class No665非递减数列 {

    /**
     * 给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
     * 我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
     *
     * 示例 1:
     * 输入: nums = [4,2,3]
     * 输出: true
     * 解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
     * 示例 2:
     * 输入: nums = [4,2,1]
     * 输出: false
     * 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
     */

    //思路没问题,自我感觉写的很复杂,后面有参照版本
    public boolean checkPossibility(int[] nums) {
        if(nums.length<3){
            return true;
        }

        if(nums.length==3){
            //自行判断 仅需一个升序即可
            return nums[0]<=nums[1]||nums[1]<=nums[2];
        }

        boolean haveChance=true;

        //需要四个元素 [i-1,(i,i+1),i+1+1]
        //所以范围 [1...nums.length-2]

        for (int i = 1; i < nums.length-2; i++) {

            int firstNum=nums[i-1];
            int thisNum=nums[i];
            int nextNum=nums[i+1];
            int lastNum=nums[i+2];

            if(thisNum>nextNum){
                //非升序
                if(!haveChance){
                    return false;
                }
                //先前再后 且都需要前后比

                thisNum=firstNum;
                if(thisNum<=nextNum){
                    //此次变更可以通过
                    nums[i]=firstNum;
                }else{
                    //不可,则改后
                    thisNum=nums[i];//复原
                    nextNum=thisNum;
                    if(nextNum<=lastNum){
                        //可以通过
                        nums[i+1]=nums[i];
                    }else{
                        //无法更改
                        return false;
                    }
                }

                haveChance=false;
            }

        }

        //如果能走到这里 还需要额外检查开头和结尾(haveChance为false)
        if(nums[0]>nums[1]&&nums[nums.length-1]<nums[nums.length-2]){
            return false;
        }
        if(nums[0]>nums[1]||nums[nums.length-1]<nums[nums.length-2]){
            return haveChance;
        }

        return true;
    }

    //参照版本:其实把我上面的 thisNum和nextNum比 改成 thisNum和lastNum比
    public boolean checkPossibilityGood(int[] nums){

        if(nums.length<3){
            return true;
        }

        boolean haveChance=true;

        for (int i = 2; i < nums.length-1; i++) {

            int thisNum=nums[i];
            int nextNum=nums[i+1];
            int frontNum=nums[i-1];
            int firstNum=nums[i-2];
            if(thisNum<frontNum){
                //非升等序

                if(!haveChance){
                    return false;
                }

                //先让前面的那个小点,或者再让当前这个大点
                if(firstNum<=thisNum){
                    nums[i-1]=nums[i-2];
                }else{

                    if(nextNum>=frontNum){
                        nums[i]=nums[i+1];
                    }else{
                        return false;
                    }

                }


                haveChance=false;
            }

        }

        //还有 前面两个元素  最后一个元素

        if(nums[0]>nums[1]&&nums[nums.length-1]<nums[nums.length-2]){
            return false;
        }

        if(nums[0]>nums[1]){
            return haveChance;
        }

        if(nums[nums.length-1]<nums[nums.length-2]){
            return haveChance;
        }

        return true;
    }

    public static void main(String[] args) {
        int[] arr={1,2,3};
        GeneralFunction generalFunction=new GeneralFunction(No665非递减数列.class,arr);
        generalFunction.runAllMethod();
    }

}
